package cn.edu.xjtu.competiton.lccp;

import cn.edu.xjtu.Util.TreeNode.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @author Hydrion-QLz
 * @date 2022-04-16 15:32
 * @description
 */
public class Third2 {
    Map<Integer, Integer> map = new HashMap<>();
    int ans = 0;

    public int getNumber(TreeNode root, int[][] ops) {
        for (int i = 0; i < ops.length; i++) {
            TreeNode node = help(root, ops[i][1], ops[i][2]);
            map.put(node.val, ops[i][0]);
        }
        getAns(root, map.getOrDefault(root.val, 0));
        return ans;
    }

    public void getAns(TreeNode root, int color) {
        if (root == null) {
            return;
        }
        color = map.getOrDefault(root.val, color);
        if (color == 1) ans++;
        getAns(root.left, color);
        getAns(root.right, color);
    }

    public TreeNode help(TreeNode root, int p, int q) {
        //都比root小，递归左子树
        if (root.val > q && root.val > p) return help(root.left, p, q);
        //都比root大，递归右子树
        if (root.val < q && root.val < p) return help(root.right, p, q);
        //都不满足上述条件，说明是最近的公共子节点了，返回这个节点
        return root;
    }
}